Search results for "Quantum algorithms"
showing 7 items of 7 documents
Quantum Algorithms for Some Strings Problems Based on Quantum String Comparator
2022
We study algorithms for solving three problems on strings. These are sorting of n strings of length k, “the Most Frequent String Search Problem”, and “searching intersection of two sequences of strings”. We construct quantum algorithms that are faster than classical (randomized or deterministic) counterparts for each of these problems. The quantum algorithms are based on the quantum procedure for comparing two strings of length k in O(k) queries. The first problem is sorting n strings of length k. We show that classical complexity of the problem is Θ(nk) for constant size alphabet, but our quantum algorithm has O˜(nk) complexity. The second one is searching the most frequent string among n …
Quadratic speedup for finding marked vertices by quantum walks
2020
A quantum walk algorithm can detect the presence of a marked vertex on a graph quadratically faster than the corresponding random walk algorithm (Szegedy, FOCS 2004). However, quantum algorithms that actually find a marked element quadratically faster than a classical random walk were only known for the special case when the marked set consists of just a single vertex, or in the case of some specific graphs. We present a new quantum algorithm for finding a marked vertex in any graph, with any set of marked vertices, that is (up to a log factor) quadratically faster than the corresponding classical random walk.
Datorzinātne un informācijas tehnoloģijas: Datu bāzes un informācijas sistēmas: doktorantu konsorcijs. Sestā Starptautiskā Baltijas konference Baltic…
2004
The Baltic Conference on Databases and Information Systems is a biannual international forum for technical discussion among researchers and developers of database and information systems. The objective of the conference is to bring together researchers as well as practitioners and PhD students in the field of computing research that will improve the construction of future information systems. On the other hand, the conference is giving opportunities to developers, users and researchers of advanced IS technologies to present their work and to exchange their ideas and at the same time providing a feedback to database community.
Variable time amplitude amplification and quantum algorithms for linear algebra problems
2012
Quantum amplitude amplification is a method of increasing a success probability of an algorithm from a small epsilon>0 to Theta(1) with less repetitions than classically. In this paper, we generalize quantum amplitude amplification to the case when parts of the algorithm that is being amplified stop at different times. We then apply the new variable time amplitude amplification to give two new quantum algorithms for linear algebra problems. Our first algorithm is an improvement of Harrow et al. algorithm for solving systems of linear equations. We improve the running time of the algorithm from O(k^2 log N) to O(k log^3 k log N) where k is the condition number of the system of equations. …
Precīzie kvantu algoritmi, izmantojot 1-kvantu-vaicājuma izsaukumus
2018
Darbā ir analizēti zināmi unikāli precīzie kvantu algoritmi, kuru īpašības ir atšķirīgas no citiem literatūrā atrodamiem algoritmiem, un uzsākts pētīt iespējas vispārināt šajos algoritmos esošos paņēmienus. Darbā ir noformulēts jauns skaitļošanas modelis, kas ir saistīts ar precīzo kvantu vaicājumu modeli. Veikti skaitliski aprēķini, lai palīdzētu saprast jaunā modeļa iespējas un ierobežojumus. Izteiktas hipotēzes un virzieni, kādos turpināt analīzi un pētījumu.
Improved constructions of mixed state quantum automata
2009
Quantum finite automata with mixed states are proved to be super-exponentially more concise rather than quantum finite automata with pure states. It was proved earlier by A. Ambainis and R. Freivalds that quantum finite automata with pure states can have an exponentially smaller number of states than deterministic finite automata recognizing the same language. There was an unpublished ''folk theorem'' proving that quantum finite automata with mixed states are no more super-exponentially more concise than deterministic finite automata. It was not known whether the super-exponential advantage of quantum automata is really achievable. We prove that there is an infinite sequence of distinct int…
Quantum algorithm complexity
2008
Elektroniskā versija nesatur pielikumus